package com.du.algorithm.primary;

import com.du.algorithm.primary.util.SortUtil;

import java.util.*;
import java.util.stream.Collectors;

/**
 * @Desc :
 * @Author: shuangdu
 * @date : 2022/10/24
 */
public class Subject {

    /**
     * 词根替换
     * @param dictionary
     * @param sentence
     * @return
     */
    public static String replaceWords(List<String> dictionary, String sentence) {
        List<String> sortDic = dictionary.stream().sorted(Comparator.comparingInt(String::length)).collect(Collectors.toList());
        String[] words = sentence.split(" ");
        String[] strs = new String[words.length];
        for (int i = 0; i<words.length; i++) {
            String w = words[i];
            for (String dic : sortDic) {
                if (w.startsWith(dic)) {
                    strs[i] = dic;
                    break;
                }
            }
            if (strs[i] == null) {
                strs[i] = w;
            }
        }
        String s = String.join(" ", strs);
        System.out.println("词根列表为:" + s);
        return s;
    }
    public static String replaceWords_(List<String> dictionary, String sentence) {
        String s = new PrefixTree().replaceWords(dictionary, sentence);
        System.out.println("词根列表为:" + s);
        return s;
    }

    /**
     * 跳水板
     * 你正在使用一堆木板建造跳水板。有两种类型的木板，其中长度较短的木板长度为shorter，长度较长的木板长度为longer。你必须正好使用k块木板。编写一个方法，生成跳水板所有可能的长度。
     *
     * 返回的长度需要从小到大排列。
     *
     * 示例 1
     *
     * 输入：
     * shorter = 1
     * longer = 2
     * k = 3
     * 输出： [3,4,5,6]
     * 解释：
     * 可以使用 3 次 shorter，得到结果 3；使用 2 次 shorter 和 1 次 longer，得到结果 4 。以此类推，得到最终结果。
     * 提示：
     *
     * 0 < shorter <= longer
     * 0 <= k <= 100000
     * @param shorter
     * @param longer
     * @param k
     * @return
     */
    public static int[] divingBoard(int shorter, int longer, int k) {
        if (k == 0) return new int[]{};
        if (shorter == longer) return new int[]{ shorter*k };
        // x(k-n) + y*n
        int[] r = new int[k + 1];
        for (int i = 0; i<=k; i++) {
            r[i] = shorter * (k - i) + longer * i;
        }
        System.out.println(Arrays.toString(r));
        return r;
    }

    /**
     * 环形房屋偷盗
     * 一个专业的小偷，计划偷窃一个环形街道上沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。
     * 同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。
     *
     * 给定一个代表每个房屋存放金额的非负整数数组 nums ，请计算 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。
     *
     *  
     *
     * 示例 1：
     *
     * 输入：nums = [2,3,2]
     * 输出：3
     * 解释：你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。
     * 示例 2：
     *
     * 输入：nums = [1,2,3,1]
     * 输出：4
     * 解释：你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。
     *      偷窃到的最高金额 = 1 + 3 = 4 。
     * 示例 3：
     *
     * 输入：nums = [0]
     * 输出：0
     *  
     *
     * 提示：
     *
     * 1 <= nums.length <= 100
     * 0 <= nums[i] <= 1000
     * @param nums
     * @return
     */
    public static int rob(int[] nums) {
        if (nums.length == 1) return nums[0];
        if (nums.length == 2) return Math.max(nums[0], nums[1]);
        int max = Math.max(rangeRob(nums, 0, nums.length - 2), rangeRob(nums, 1, nums.length - 1));
        System.out.println("max:" + max);
        return max;
    }
    private static int rangeRob(int[] nums, int start, int end) {
        int first = nums[start], second = Math.max(nums[start], nums[start+1]);
        for (int i = start + 2; i <= end; i++) {
            int temp = second;
            second = Math.max(first + nums[i], second);
            first = temp;
        }
        return second;
    }

    /**
     * 优势洗牌
     * 给定两个大小相等的数组 nums1 和 nums2，nums1 相对于 nums2 的优势可以用满足 nums1[i] > nums2[i] 的索引 i 的数目来描述。
     *
     * 返回 nums1 的任意排列，使其相对于 nums2 的优势最大化。
     *  
     *
     * 示例 1：
     *
     * 输入：nums1 = [2,7,11,15], nums2 = [1,10,4,11]
     * 输出：[2,11,7,15]
     * 示例 2：
     *
     * 输入：nums1 = [12,24,8,32], nums2 = [13,25,32,11]
     * 输出：[24,32,8,12]
     *  
     *
     * 提示：
     *
     * 1 <= nums1.length <= 105
     * nums2.length == nums1.length
     * 0 <= nums1[i], nums2[i] <= 109
     * @param nums1
     * @param nums2
     * @return
     */
    public static int[] advantageCount(int[] nums1, int[] nums2) {
        Integer[] idx = new Integer[nums2.length];
        for (int i = 0; i<nums2.length;i++) idx[i] = i;
        Arrays.sort(nums1);
        Arrays.sort(idx, Comparator.comparingInt(a -> nums2[a]));

        int L = 0, R = nums2.length - 1;
        for (int i : nums1) {
            if (i > nums2[idx[L]]) {
                nums2[idx[L++]] = i;
            } else {
                nums2[idx[R--]] = i;
            }
        }

        System.out.println(Arrays.toString(nums2));
        return nums2;
    }

    /**
     * 整数反转
     * 给你一个 32 位的有符号整数 x ，返回将 x 中的数字部分反转后的结果。
     *
     * 如果反转后整数超过 32 位的有符号整数的范围 [−231,  231 − 1] ，就返回 0。
     *
     * 假设环境不允许存储 64 位整数（有符号或无符号）。
     *
     * 示例 1：
     *
     * 输入：x = 123
     * 输出：321
     * 示例 2：
     *
     * 输入：x = -123
     * 输出：-321
     * 示例 3：
     *
     * 输入：x = 120
     * 输出：21
     * 示例 4：
     *
     * 输入：x = 0
     * 输出：0
     *
     * 提示：
     *
     * -2^31 <= x <= 2^31 - 1
     * @param x
     * @return
     */
    public static int reverseNumber(int x) {
        // x每次 % 10获取最后一位数
        int in = x;
        int res = 0;
        int last;
        while (x != 0) {
            int temp = x % 10;
            last = res;
            res = res * 10 + temp;
            // 判断整数溢出
            if (last != res / 10) {
                System.out.println(in + "反转溢出!");
                return 0;
            }
            x /= 10;
        }

        System.out.println(in + "反转为：" + res);
        return res;
    }

    /**
     * 回文数
     * 给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。
     *
     * 回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。
     *
     * 例如，121 是回文，而 123 不是。
     *  
     * 示例 1：
     *
     * 输入：x = 121
     * 输出：true
     * 示例 2：
     *
     * 输入：x = -121
     * 输出：false
     * 解释：从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。
     * 示例 3：
     *
     * 输入：x = 10
     * 输出：false
     * 解释：从右向左读, 为 01 。因此它不是一个回文数。
     *  
     * 提示：
     *
     * -2^31 <= x <= 2^31 - 1
     * @param x
     * @return
     */
    public static boolean isPalindrome(int x) {
        if (x < 0) {
            System.out.println("负数不是回文数");
            return false;
        }
        int in = x;
        int res = 0;
        while (x != 0) {
            int temp = x % 10;
            res = res * 10 + temp;
            x /= 10;
        }
        boolean flag = res == in;
        System.out.println(in + "是回文数? " + flag);
        return flag;
    }

    /**
     * 最高建筑高度
     * 在一座城市里，你需要建 n 栋新的建筑。这些新的建筑会从 1 到 n 编号排成一列。
     *
     * 这座城市对这些新建筑有一些规定：
     *
     * 每栋建筑的高度必须是一个非负整数。
     * 第一栋建筑的高度 必须 是 0 。
     * 任意两栋相邻建筑的高度差 不能超过  1 。
     * 除此以外，某些建筑还有额外的最高高度限制。这些限制会以二维整数数组 restrictions 的形式给出，其中 restrictions[i] = [idi, maxHeighti] ，表示建筑 idi 的高度 不能超过 maxHeighti 。
     *
     * 题目保证每栋建筑在 restrictions 中 至多出现一次 ，同时建筑 1 不会 出现在 restrictions 中。
     *
     * 请你返回 最高 建筑能达到的 最高高度 。
     * @param n
     * @param restrictions
     * @return
     */
    public static int maxBuilding(int n, int[][] restrictions) {
        int[] index = new int[n];
        for (int i = 0; i < n; i++) {
            index[i] = 0;
            for (int[] r : restrictions) {
                if (r[0] == (i+1)) {
                    index[i] = r[1];
                    break;
                }
            }
        }
        int[][] dp = new int[n][2];
        dp[0][0] = 0;
        dp[0][1] = 1;
        int max = 0;
        for (int i = 0; i < n; i++) {
            if (i == 0) continue;

            max = Math.max(max, index[i]);
        }
        System.out.println(Arrays.toString(index));
        System.out.println("最高高度: " + max);
        return max;
    }

    /**
     * 盛最多水的容器
     * 给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
     *
     * 找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
     *
     * 返回容器可以储存的最大水量。
     *
     * 说明：你不能倾斜容器。 
     *
     * 示例 1：
     *
     * 输入：[1,8,6,2,5,4,8,3,7]
     * 输出：49
     * 解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水的最大值为 49。
     * 示例 2：
     *
     * 输入：height = [1,1]
     * 输出：1
     * @param height
     * @return
     */
    public static int maxAreaNum(int[] height) {
        // 双指针
        int l = 0, r = height.length - 1;
        int res = 0;
        while (l < r) {
            System.out.print(String.format("l: %s, r: %s", l, r));
            res = height[l] > height[r] ? Math.max(res, (r - l) * height[r--]) : Math.max(res, (r - l) * height[l++]);
            System.out.println(" 面积" + res);
        }
        System.out.println("最大面积为：" + res);
        return res;
    }

    /**
     * 整数转罗马数字
     * 罗马数字包含以下七种字符： I， V， X， L，C，D 和 M。
     *
     * 字符          数值
     * I             1
     * V             5
     * X             10
     * L             50
     * C             100
     * D             500
     * M             1000
     * 例如， 罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做  XXVII, 即为 XX + V + II 。
     *
     * 通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。
     * 数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：
     *
     * I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
     * X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。 
     * C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。
     * 给你一个整数，将其转为罗马数字。
     *
     *
     * 示例 1:
     *
     * 输入: num = 3
     * 输出: "III"
     * 示例 2:
     *
     * 输入: num = 4
     * 输出: "IV"
     * 示例 3:
     *
     * 输入: num = 9
     * 输出: "IX"
     * 示例 4:
     *
     * 输入: num = 58
     * 输出: "LVIII"
     * 解释: L = 50, V = 5, III = 3.
     * 示例 5:
     *
     * 输入: num = 1994
     * 输出: "MCMXCIV"
     * 解释: M = 1000, CM = 900, XC = 90, IV = 4.
     *
     * 提示：
     *
     * 1 <= num <= 3999
     * @param num
     * @return
     */
    public static String intToRoman(int num) {
        int[] a = new int[]{1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
        String[] b = new String[]{"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < a.length; i++) {
            while (num >= a[i]) {
                num -= a[i];
                sb.append(b[i]);
            }
            if (num == 0) {
                break;
            }
        }
        System.out.println("罗马字为：" + sb);
        return sb.toString();
    }

    /**
     * 罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。
     *
     * 字符          数值
     * I             1
     * V             5
     * X             10
     * L             50
     * C             100
     * D             500
     * M             1000
     * 例如， 罗马数字 2 写做 II ，即为两个并列的 1 。12 写做 XII ，即为 X + II 。 27 写做  XXVII, 即为 XX + V + II 。
     *
     * 通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，
     * 例如 4 不写做 IIII，而是 IV。
     * 数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。
     * 同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：
     *
     * I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
     * X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。 
     * C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。
     * 给定一个罗马数字，将其转换成整数。
     *
     * 示例 1:
     *
     * 输入: s = "III"
     * 输出: 3
     * 示例 2:
     *
     * 输入: s = "IV"
     * 输出: 4
     * 示例 3:
     *
     * 输入: s = "IX"
     * 输出: 9
     * 示例 4:
     *
     * 输入: s = "LVIII"
     * 输出: 58
     * 解释: L = 50, V= 5, III = 3.
     * 示例 5:
     *
     * 输入: s = "MCMXCIV"
     * 输出: 1994
     * 解释: M = 1000, CM = 900, XC = 90, IV = 4.
     *
     * 提示：
     *
     * 1 <= s.length <= 15
     * s 仅含字符 ('I', 'V', 'X', 'L', 'C', 'D', 'M')
     * 题目数据保证 s 是一个有效的罗马数字，且表示整数在范围 [1, 3999] 内
     * 题目所给测试用例皆符合罗马数字书写规则，不会出现跨位等情况。
     * IL 和 IM 这样的例子并不符合题目要求，49 应该写作 XLIX，999 应该写作 CMXCIX 。
     * 关于罗马数字的详尽书写规则，可以参考 罗马数字 - Mathematics 。
     * @param s
     * @return
     */
    public static int romanToInt(String s) {
        HashMap<Character, Integer> map = new HashMap<>();
        map.put('I', 1);
        map.put('V', 5);
        map.put('X', 10);
        map.put('L', 50);
        map.put('C', 100);
        map.put('D', 500);
        map.put('M', 1000);

        char[] c = s.toCharArray();
        int ans = 0;
        for (int i = 0; i < c.length; i++) {
            Integer val = map.get(s.charAt(i));
            if (i + 1 < c.length && val < map.get(s.charAt(i+1))) {
                ans -= val;
            } else {
                ans += val;
            }
        }
        System.out.println(ans);
        return ans;
    }

    /**
     * 三数之和
     * 给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请
     *
     * 你返回所有和为 0 且不重复的三元组。
     *
     * 注意：答案中不可以包含重复的三元组。
     *
     * 示例 1：
     *
     * 输入：nums = [-1,0,1,2,-1,-4]
     * 输出：[[-1,-1,2],[-1,0,1]]
     * 解释：
     * nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
     * nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
     * nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
     * 不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
     * 注意，输出的顺序和三元组的顺序并不重要。
     * 示例 2：
     *
     * 输入：nums = [0,1,1]
     * 输出：[]
     * 解释：唯一可能的三元组和不为 0 。
     * 示例 3：
     *
     * 输入：nums = [0,0,0]
     * 输出：[[0,0,0]]
     * 解释：唯一可能的三元组和为 0 。
     *  
     *
     * 提示：
     *
     * 3 <= nums.length <= 3000
     * -10^5 <= nums[i] <= 10^5
     * @param nums
     * @return
     */
    public static List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> list = new ArrayList<>();
        if (nums.length < 3) return list;
        // 双指针解法
        // 排序
        SortUtil.fastSort(nums);
        for (int i = 0; i < nums.length; i++) {
            // 重复元素跳过
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            int left = i + 1;
            int right = nums.length - 1;
            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                if (sum > 0) {
                    // right指针左移
                    right--;
                } else if (sum < 0) {
                    // left指针右移
                    left++;
                } else {
                    // 三个数相加为0
                    List<Integer> l = new ArrayList<>();
                    l.add(nums[i]);
                    l.add(nums[left]);
                    l.add(nums[right]);
                    list.add(l);

                    right--;
                    left++;
                    // 重复元素跳过
                    while (right > left && nums[right] == nums[right + 1]) {
                        right--;
                    }
                    while (left < right && nums[left] == nums[left - 1]) {
                        left++;
                    }
                }
            }
        }

        System.out.println(list);
        return list;
    }

    /**
     * 最接近的三数之和
     * 给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数，使它们的和与 target 最接近。
     *
     * 返回这三个数的和。
     *
     * 假定每组输入只存在恰好一个解。
     *
     * 示例 1：
     *
     * 输入：nums = [-1,2,1,-4], target = 1
     * 输出：2
     * 解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。
     * 示例 2：
     *
     * 输入：nums = [0,0,0], target = 1
     * 输出：0
     *
     * 提示：
     * 3 <= nums.length <= 1000
     * -1000 <= nums[i] <= 1000
     * -10^4 <= target <= 10^4
     * @param nums
     * @param target
     * @return
     */
    public static int threeSumClosest(int[] nums, int target) {
        // 排序，双指针
        SortUtil.fastSort(nums);
        int ans = 0;
        for (int i = 0; i < nums.length; i++) {
            int left = i + 1;
            int right = nums.length - 1;
            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                if (Math.abs(Math.abs(target) - Math.abs(sum)) <  Math.abs(Math.abs(target) - Math.abs(ans))) {
                    ans = sum;
                    System.out.println(String.format("三个数为：[%s,%s,%s]", nums[i], nums[left], nums[right]));
                }
                if (sum > target) {
                    // right左移
                    right--;
                } else if (sum < target) {
                    // left右移
                    left++;
                } else {
                    System.out.println(String.format("三个数为：[%s,%s,%s]", nums[i], nums[left], nums[right]));
                    ans = sum;
                    System.out.println("合为:" + sum);
                    return ans;
                }
            }
        }

        System.out.println("目标值：" + target);
        return ans;
    }

    public static void main(String[] args) {
        List<String> dictionary = Arrays.asList("a","ab", "abn", "i");
        String sentence = "it is abnormal that this solution is accepted";
        LogTool.exec("词根替换", () -> replaceWords(dictionary, sentence));
        LogTool.exec("(优化)词根替换", () -> replaceWords_(dictionary, sentence));
        LogTool.exec("跳水板", () -> divingBoard(1, 3, 4));

        LogTool.exec("环形房屋偷盗", () -> rob(new int[]{3, 2, 2}));

        LogTool.exec("优势洗牌", () -> advantageCount(new int[]{12,24,8,32}, new int[]{13,25,32,11}));

        LogTool.exec("最高建筑高度", () -> maxBuilding(10, new int[][]{new int[]{5, 3},new int[]{2, 5},new int[]{7, 4},new int[]{10, 3}}));

        LogTool.exec("整数反转", () -> reverseNumber(-214748364));

        LogTool.exec("回文数", () -> isPalindrome(12321));

        LogTool.exec("盛最多水的容器", () -> maxAreaNum(new int[]{1,5,6,1,3,7,8,2,1}));

        LogTool.exec("整数转罗马数字", () -> intToRoman(999));

        LogTool.exec("罗马转整数数字", () -> romanToInt("CMXCIX"));

        LogTool.exec("三数之和", () -> threeSum(new int[]{-1,0,1,2,-1,-4,-2,-3,3,0,4}));

        LogTool.exec("最接近的三数之和", () -> threeSumClosest(new int[]{4,0,5,-5,9,-3,0,-4,-5,1}, 19));
    }

}
